#ifndef __QUEUE__
#define __QUEUE__
#include<iostream>

// 头节点为空节点，next 指向 队首
// 根据头节点获得 队首
// queue(head) -> n0 -> n1 -> n2 -> .... -> nullptr

/*
* 通过链表实现
*/
template<typename T>
struct QueueList {
	QueueList* Next;
	T Data;
};

//添加元素至队尾
template<typename T>
void Push(QueueList<T>* queueTop, const T& data) {
	QueueList<T>* node = new QueueList<T>();
	node->Data = data;
	node->Next = nullptr;

	//查找队尾
	if (queueTop->Next == nullptr) {
		queueTop->Next = node;
		return;
	}

	QueueList<T>* pQueue = queueTop->Next;
	while (pQueue->Next != nullptr) {
		pQueue = pQueue->Next;
	}
	pQueue->Next = node;
}

//取出队首元素
template<typename T>
void Pop(QueueList<T>* queueTop) {
	QueueList<T>* top = queueTop->Next;
	queueTop->Next = top->Next;

	top->Next = nullptr;
	delete top;
}

template<typename T>
void PrintQueue(QueueList<T>* queueTop) {
	QueueList<T>* pQueue = queueTop->Next;
	while (pQueue != nullptr) {
		std::cout << pQueue->Data << " -> ";
		pQueue = pQueue->Next;
	}
	std::cout << "nullptr" << std::endl;
}

#endif // !__QUEUE__
